﻿namespace LearnDSSortings;

/// <summary>
/// 计数排序
/// </summary>
public class CountSort
{
    public void Sort(int[] arr)
    {
        int n = arr.Length;
        int maxValue = GetMaxValue(arr);
        int[] carry = new int[maxValue + 1];
        for (int i = 0; i < n; i++)
        {
            carry[arr[i]] = carry[arr[i]] + 1;
        }

        int x = 0;
        int y = 0;
        while (x < maxValue + 1)
        {
            if (carry[x] > 0)
            {
                arr[y++] = x;
                carry[x] = carry[x] - 1;
            }
            else
            {
                x++;
            }
        }
    }

    public int GetMaxValue(int[] arr)
    {
        int maxValue = int.MinValue;
        for (int i = 0; i < arr.Length; i++)
        {
            maxValue = Math.Max(arr[i], maxValue);
        }

        return maxValue;
    }
}